//2546. 执行逐位运算使字符串相等

//给你两个下标从 0 开始的 二元 字符串 s 和 target ，两个字符串的长度均为 n 。你可以对 s 执行下述操作 任意 次：
//选择两个 不同 的下标 i 和 j ，其中 0 <= i, j < n 。
//同时，将 s[i] 替换为(s[i] OR s[j]) ，s[j] 替换为(s[i] XOR s[j]) 。
//例如，如果 s = "0110" ，你可以选择 i = 0 和 j = 2，然后同时将 s[0] 替换为(s[0] OR s[2] = 0 OR 1 = 1)，并将 s[2] 替换为(s[0] XOR s[2] = 0 XOR 1 = 1)，最终得到 s = "1110" 。
//如果可以使 s 等于 target ，返回 true ，否则，返回 false 。

//class Solution {
//public:
//    bool makeStringsEqual(string s, string target) { // 有 1 就行
//        return (s.find('1') == string::npos) == (target.find('1') == string::npos);
//    }
//};

//1558. 得到目标数组的最少函数调用次数

//给你一个与 nums 大小相同且初始值全为 0 的数组 arr ，请你调用以上函数得到整数数组 nums 。
//请你返回将 arr 变成 nums 的最少函数调用次数。
//答案保证在 32 位有符号整数以内。

//class Solution {
//public:
//    int minOperations(vector<int>& nums) {
//        int ans = 0, maxn = 0;
//        for (auto num : nums) {
//            maxn = max(maxn, num);
//            ans += popcount(static_cast<uint32_t>(num));
//        }
//        if (maxn > 0) {
//            ans += 31 - countl_zero(static_cast<uint32_t>(maxn));
//        }
//        return ans;
//    }
//};

//2571. 将整数减少到零需要的最少操作数

//给你一个正整数 n ，你可以执行下述操作 任意 次：
//n 加上或减去 2 的某个 幂
//返回使 n 等于 0 需要执行的 最少 操作数。
//如果 x == 2i 且其中 i >= 0 ，则数字 x 是 2 的幂。

//class Solution {
//public:
//    int minOperations(int n) {
//        int ans = 1;
//        while (n & (n - 1)) { // n 不是 2 的幂次
//            int lb = n & -n;
//            if (n & (lb << 1)) n += lb; // 多个连续 1
//            else n -= lb; // 单个 1
//            ++ans;
//        }
//        return ans;
//    }
//};

//3315. 构造最小位运算数组 II

//给你一个长度为 n 的质数数组 nums 。你的任务是返回一个长度为 n 的数组 ans ，对于每个下标 i ，以下 条件 均成立：
//ans[i] OR(ans[i] + 1) == nums[i]
//除此以外，你需要 最小化 结果数组里每一个 ans[i] 。
//如果没法找到符合 条件 的 ans[i] ，那么 ans[i] = -1 。
//质数 指的是一个大于 1 的自然数，且它只有 1 和自己两个因数。

//class Solution {
//public:
//    vector<int> minBitwiseArray(vector<int>& nums) {
//        for (int& x : nums) { // 注意这里是引用
//            if (x == 2) {
//                x = -1;
//            }
//            else {
//                int t = ~x;
//                x ^= (t & -t) >> 1;
//            }
//        }
//        return nums;
//    }
//};

//2568. 最小无法得到的或值

//给你一个下标从 0 开始的整数数组 nums 。
//如果存在一些整数满足 0 <= index1 < index2 < ... < indexk < nums.length ，得到 nums[index1] | nums[index2] | ... | nums[indexk] = x ，那么我们说 x 是 可表达的 。
//换言之，如果一个整数能由 nums 的某个子序列的或运算得到，那么它就是可表达的。
//请你返回 nums 不可表达的 最小非零整数 。

//class Solution {
//public:
//    int minImpossibleOR(vector<int>& nums) {
//        int mask = 0;
//        for (int x : nums) {
//            if ((x & (x - 1)) == 0) { // x 是 2 的幂次
//                mask |= x;
//            }
//        }
//        mask = ~mask;
//        return mask & -mask; // lowbit
//    }
//};

//2509. 查询树中环的长度

//给你一个整数 n ，表示你有一棵含有 2n - 1 个节点的 完全二叉树 。根节点的编号是 1 ，树中编号在[1, 2n - 1 - 1] 之间，编号为 val 的节点都有两个子节点，满足：
//左子节点的编号为 2 * val
//右子节点的编号为 2 * val + 1
//给你一个长度为 m 的查询数组 queries ，它是一个二维整数数组，其中 queries[i] = [ai, bi] 。对于每个查询，求出以下问题的解：
//在节点编号为 ai 和 bi 之间添加一条边。
//求出图中环的长度。
//删除节点编号为 ai 和 bi 之间新添加的边。
//注意：
//环 是开始和结束于同一节点的一条路径，路径中每条边都只会被访问一次。
//环的长度是环中边的数目。
//在树中添加额外的边后，两个点之间可能会有多条边。
//请你返回一个长度为 m 的数组 answer ，其中 answer[i] 是第 i 个查询的结果。

//class Solution {
//public:
//    vector<int> cycleLengthQueries(int n, vector<vector<int>>& queries) {
//        int m = queries.size();
//        vector<int> ans(m);
//        for (int i = 0; i < m; ++i) {
//            int a = queries[i][0], b = queries[i][1];
//            if (a > b) swap(a, b); // 保证 a <= b
//            int d = countl_zero(static_cast<uint32_t>(a)) - countl_zero(static_cast<uint32_t>(b));
//            b >>= d; // 上跳，和 a 在同一层
//            ans[i] = a == b ? d + 1 : d + (32 - countl_zero(static_cast<uint32_t>(a ^ b))) * 2 + 1;
//        }
//        return ans;
//    }
//};

//2939. 最大异或乘积

//给你三个整数 a ，b 和 n ，请你返回(a XOR x)* (b XOR x) 的 最大值 且 x 需要满足 0 <= x < 2n。
//由于答案可能会很大，返回它对 109 + 7 取余 后的结果。
//注意，XOR 是按位异或操作。

//class Solution {
//public:
//    int maximumXorProduct(long long a, long long b, int n) {
//        if (a < b) {
//            swap(a, b); // 保证 a >= b
//        }
//
//        long long mask = (1LL << n) - 1;
//        long long ax = a & ~mask; // 第 n 位及其左边，无法被 x 影响，先算出来
//        long long bx = b & ~mask;
//        a &= mask; // 低于第 n 位，能被 x 影响
//        b &= mask;
//
//        long long left = a ^ b; // 可分配：a XOR x 和 b XOR x 一个是 1 另一个是 0
//        long long one = mask ^ left; // 无需分配：a XOR x 和 b XOR x 均为 1
//        ax |= one; // 先加到异或结果中
//        bx |= one;
//
//        // 现在要把 left 分配到 ax 和 bx 中
//        // 根据基本不等式（均值定理），分配后应当使 ax 和 bx 尽量接近，乘积才能尽量大
//        if (left > 0 && ax == bx) {
//            // 尽量均匀分配，例如把 1111 分成 1000 和 0111
//            long long high_bit = 1LL << (63 - __builtin_clzll(left));
//            ax |= high_bit;
//            left ^= high_bit;
//        }
//        // 如果 a & ~mask 更大，则应当全部分给 bx（注意最上面保证了 a>=b）
//        bx |= left;
//
//        const long long MOD = 1'000'000'007;
//        return ax % MOD * (bx % MOD) % MOD; // 注意不能直接 LL * LL，否则溢出
//    }
//};

//2749. 得到整数零需要执行的最少操作数

//给你两个整数：num1 和 num2 。
//在一步操作中，你需要从范围[0, 60] 中选出一个整数 i ，并从 num1 减去 2i + num2 。
//请你计算，要想使 num1 等于 0 需要执行的最少操作数，并以整数形式返回。
//如果无法使 num1 等于 0 ，返回 - 1 。

//class Solution {
//public:
//    int makeTheIntegerZero(int num1, int num2) {
//        for (long long k = 1; k <= num1 - num2 * k; k++) {
//            if (k >= popcount(static_cast<uint64_t>(num1) - num2 * k)) {
//                return k;
//            }
//        }
//        return -1;
//    }
//};

//2835. 使子序列的和等于目标的最少操作次数

//给你一个下标从 0 开始的数组 nums ，它包含 非负 整数，且全部为 2 的幂，同时给你一个整数 target 。
//一次操作中，你必须对数组做以下修改：
//选择数组中一个元素 nums[i] ，满足 nums[i] > 1 。
//将 nums[i] 从数组中删除。
//在 nums 的 末尾 添加 两个 数，值都为 nums[i] / 2 。
//你的目标是让 nums 的一个 子序列 的元素和等于 target ，请你返回达成这一目标的 最少操作次数 。如果无法得到这样的子序列，请你返回 - 1 。
//数组中一个 子序列 是通过删除原数组中一些元素，并且不改变剩余元素顺序得到的剩余数组。

//class Solution {
//public:
//    int minOperations(vector<int>& nums, int target) {
//        if (accumulate(nums.begin(), nums.end(), 0LL) < target) {
//            return -1;
//        }
//        int cnt[31]{};
//        for (int x : nums) {
//            cnt[__builtin_ctz(x)]++;
//        }
//        int ans = 0, i = 0;
//        long long s = 0;
//        while ((1LL << i) <= target) {
//            s += (long long)cnt[i] << i;
//            int mask = (1ll << ++i) - 1;
//            if (s >= (target & mask)) {
//                continue;
//            }
//            ans++; // 一定要找更大的数操作
//            for (; cnt[i] == 0; i++) {
//                ans++; // 还没找到，继续找更大的数
//            }
//        }
//        return ans;
//    }
//};

//2897. 对数组执行操作使平方和最大

//给你一个下标从 0 开始的整数数组 nums 和一个 正 整数 k 。
//你可以对数组执行以下操作 任意次 ：
//选择两个互不相同的下标 i 和 j ，同时 将 nums[i] 更新为(nums[i] AND nums[j]) 且将 nums[j] 更新为(nums[i] OR nums[j]) ，OR 表示按位 或 运算，AND 表示按位 与 运算。
//你需要从最终的数组里选择 k 个元素，并计算它们的 平方 之和。
//请你返回你可以得到的 最大 平方和。
//由于答案可能会很大，将答案对 109 + 7 取余 后返回。

//class Solution {
//public:
//    int maxSum(vector<int>& nums, int k) {
//        int mod = 1'000'000'007;
//        int cnt[30]{};
//        for (int x : nums) {
//            for (int i = 0; i < 30; i++) {
//                cnt[i] += (x >> i) & 1;
//            }
//        }
//        long long ans = 0;
//        while (k--) {
//            int x = 0;
//            for (int i = 0; i < 30; i++) {
//                if (cnt[i] > 0) {
//                    cnt[i]--;
//                    x |= 1 << i;
//                }
//            }
//            ans = (ans + (long long)x * x) % mod;
//        }
//        return ans;
//    }
//};

//810. 黑板异或游戏

//黑板上写着一个非负整数数组 nums[i] 。
//Alice 和 Bob 轮流从黑板上擦掉一个数字，Alice 先手。如果擦除一个数字后，剩余的所有数字按位异或运算得出的结果等于 0 的话，当前玩家游戏失败。 
//另外，如果只剩一个数字，按位异或运算得到它本身；如果无数字剩余，按位异或运算结果为 0。
//并且，轮到某个玩家时，如果当前黑板上所有数字按位异或运算结果等于 0 ，这个玩家获胜。
//假设两个玩家每步都使用最优解，当且仅当 Alice 获胜时返回 true。

//class Solution {
//public:
//    bool xorGame(vector<int>& nums) {
//        if (nums.size() % 2 == 0) { // 偶数必赢
//            return true;
//        }
//        int xorsum = 0;
//        for (int num : nums) {
//            xorsum ^= num;
//        }
//        return xorsum == 0; // 单数看初始
//    }
//};